package primary.code06_graph;

import java.util.*;

/**
 * 最小生成数算法，Kruskal 算法
 *
 * 用权值总计最小的边连通所有节点
 *
 * 思路：
 * 初始化 边最小堆
 * 初始化 点所在集合映射
 * 初始化 边集结果
 * while 堆不为空
 *      弹出边
 *      检查边所在的俩点是否同一集合
 *      不是同一集合则保存该边并合并俩节点所在集合，是则丢弃
 * end
 */
public class Code05_Kruskal {
    static class Myset {
        public Map<Node, Set<Node>> nodeSetMap;

        public Myset(Graph graph) {
            Collection<Node> nodes = graph.nodes.values();
            nodeSetMap = new HashMap<>();
            for (Node node : nodes) {
                final HashSet<Node> set = new HashSet<>();
                set.add(node);
                nodeSetMap.put(node, set);
            }
        }

        /**
         * 将 from 节点和 to 节点所在的群落进行合并
         *
         * @param from
         * @param to
         */
        public void merge(Node from, Node to) {
            Set<Node> fromSet = nodeSetMap.get(from);
            Set<Node> toSet = nodeSetMap.get(to);
            for (Node node : fromSet) {
                nodeSetMap.put(node, toSet);
                toSet.add(node);
            }
        }

        /**
         * 判断两个节点是否在同一个群落里
         *
         * @param o1
         * @param o2
         * @return
         */
        public boolean isSameSet(Node o1, Node o2) {
            if (o1 != null && o2 != null) {
                Set<Node> s1 = nodeSetMap.get(o1);
                Set<Node> s2 = nodeSetMap.get(o2);
                return (s1 != null && s2 != null && s1 == s2) ? true : false;
            }
            return false;
        }
    }

    static class MySetTest {
        Map<Node, Set<Node>> nodeSetMap = new HashMap<>();

        public MySetTest(Graph g) {
            for (Node node : g.nodes.values()) {
                nodeSetMap.put(node,new HashSet<>(Arrays.asList(node)));
            }
        }

        boolean isConnected(Node n1, Node n2) {
            return nodeSetMap.get(n1)==nodeSetMap.get(n2);
        }

        void connect(Node n1, Node n2) {
            boolean isConnected = isConnected(n1, n2);
            if (isConnected) return;
            Set<Node> nodes1 = nodeSetMap.get(n1);
            Set<Node> nodes2 = nodeSetMap.get(n2);

            for (Node node : nodes2) {
                nodes1.add(node);
                nodeSetMap.put(node,nodes1);
            }
        }
    }

    /**
     * 从边的角度出发
     * 每次获取最小的边，假如不构成环则加入结果中
     *
     * @param g
     * @return
     */
    public static List<Edge> kruskal(Graph g) {
        List<Edge> res = new ArrayList<>();
        //将所有边添加到优先队列中
        final PriorityQueue<Edge> edges = new PriorityQueue<>();
        for (Edge edge : g.edges) {
            edges.add(edge);
        }
        //构建并查集
        Myset set = new Myset(g);
        //从小至大遍历所有边
        while (!edges.isEmpty()) {
            final Edge edge = edges.poll();
            Node from = edge.from;
            Node to = edge.to;
            if (!set.isSameSet(from, to)) {
                set.merge(from, to);
                res.add(edge);
            }
        }
        return res;
    }

    public static List<Edge> kruskalTest(Graph g) {
        MySetTest mySetTest = new MySetTest(g);
        List<Edge> res = new ArrayList<>();
        PriorityQueue<Edge> edgePriorityQueue = new PriorityQueue<>();
        for (Edge edge : g.edges) {
            edgePriorityQueue.add(edge);
        }
        while (!edgePriorityQueue.isEmpty()) {
            Edge cur = edgePriorityQueue.poll();
            Node n1 = cur.from;
            Node n2 = cur.to;
            boolean isConnected = mySetTest.isConnected(n1, n2);
            if (!isConnected) {
                res.add(cur);
                mySetTest.connect(n1, n2);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] arr = {
                {25, 1, 2},
                {25, 2, 1},

                {2, 1, 3},
                {2, 3, 1},

                {7, 1, 4},
                {7, 4, 1},

                {16, 2, 3},
                {16, 3, 2},

                {20, 2, 4},
                {20, 4, 2},

                {11, 4, 3},
                {11, 3, 4}
        };
        Graph graph = GraphUtils.transferGraph(arr);
        List<Edge> list = kruskal(graph);
        List<Edge> listTest = kruskalTest(graph);

        System.out.print("demo: ");
        for (Edge e : list) {
            System.out.print("\t" + e.weight);
        }
        System.out.println();
        System.out.print("test: ");
        for (Edge e : listTest) {
            System.out.print("\t" + e.weight);
        }
    }
}
